package code;

import java.util.HashMap;
import java.util.Map;


public class SumOfLeaf {
	static public class TreeNode{
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x){
			val=x;
		}
	}
	public int sumNumbers(TreeNode root){
		Map<TreeNode,TreeNode> parent=new HashMap<TreeNode,TreeNode>();
		TreeNode node=root;
		parent.put(root, null);
		int sum=dfs(node,parent);
		return sum;
	}
	public int dfs(TreeNode u,Map<TreeNode,TreeNode> pre){
		if(u.left==null && u.right==null){
			int digital=0;
			StringBuilder sb=new StringBuilder();
			while(u!=null){
				sb.insert(0, u.val);
				u=pre.get(u);
			}
			System.out.println(sb.toString());
			return Integer.parseInt(sb.toString());
		}
		int sum=0;
		if(u.left!=null){
			pre.put(u.left, u);
			sum+=dfs(u.left,pre);
		}
		if(u.right!=null){
			pre.put(u.right, u);
			sum+=dfs(u.right,pre);
		}
		return sum;
	}
	
	public static void main(String[] args){
		TreeNode root=new TreeNode(1);
//		TreeNode a=new TreeNode(2);
//		TreeNode b=new TreeNode(3);
//		root.left=a;
//		root.right=b;
		SumOfLeaf sol=new SumOfLeaf();
		System.out.println(sol.sumNumbers(root));
		
	}
}
